package practise.alogrithm.gotoSiliconValley.array;

import java.util.Arrays;

/**
 * find out the top K numbers in a array, there we use the idea that is used in quickly sort.
 * Every time we partition the array, and return the sorted index of the first number.
 */
public class TopKI {
    public int[] getTopK(int[] array, int k){
        int idx=0,start=0,end=array.length-1;
        if(array.length<k){
            throw new IllegalArgumentException();
        }
        idx = partitionByFirstNumber(array,start,end);
        while(idx!=k-1){
            if(idx<k-1){
                start=idx+1;//exclude the current Kth number
                idx = partitionByFirstNumber(array,start,end);
            }
            else {
                end = idx-1;//exclude the current Kth number
                idx = partitionByFirstNumber(array,start,end);
            }
        }
        return Arrays.copyOfRange(array,0,k-1);
    }

    private int partitionByFirstNumber(int[] array, int start, int end){
        int index=start;
        start++;
        while(start<=end){// equal mean end is next to start
            if(array[index]<array[start]){
                swap(array,start,end++);
            }
            if(array[index]==array[start]){
                index++;start++;
            }
            if(array[index]>array[start]){
                swap(array,start++,index++);
            }
        }
        return index;
    }

    private void swap(int[] array, int indexA, int indexB){
        int temp = array[indexA];
        array[indexA]=array[indexB];
        array[indexB]=temp;
    }
}
